Search Results

1. P. Kaski, A. Penttinen and J. Suomela, Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum Weight Independent Set in Local Conflict Graphs, Ad Hoc & Sensor Wireless Networks: An International Journal, vol. 6, 3--4, pp. 239-263, 2008 (link)(bib)

   Abstract: We study the algorithmic problem of coordinating transmissions in a wireless network where radio interference constrains concurrent transmissions on wireless links. We focus on pairwise conflicts between the links; these can be described as a conflict graph. Associated with the conflict graph are two fundamental network coordination tasks: (a) finding a nonconflicting set of links with the maximum total weight, and (b) finding a link schedule with the minimum total length. Our work shows that two assumptions on the geometric structure of conflict graphs suffice to achieve polynomialtime constant-factor approximations: (i) bounded density of devices, and (ii) bounded range of interference. We also show that these assumptions are not sufficient to obtain a polynomial-time approximation scheme (PTAS) for either coordination task. There exists a PTAS if we make an additional assumption: (iii) bounded range of radio transmissions.